package it.storm.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 01.08. 零矩阵
 * https://leetcode-cn.com/problems/zero-matrix-lcci/
 */
public class Solutions_mianshi_01_08 {
    public static void main(String[] args) {
        int[][] matrix1 = {{1, 1, 1},
                           {1, 0, 1},
                           {1, 1, 1}};  // output: {{1, 0, 1},
//                                                  {0, 0, 0},
//                                                  {1, 0, 1}}

        int[][] matrix2 = {{0, 1, 2, 0},
                           {3, 4, 5, 2},
                           {1, 3, 1, 5}};  // output: {{0, 0, 0, 0},
//                                                     {0, 4, 5, 0},
//                                                     {0, 3, 1, 0}}


        List<int[][]> inputs = new ArrayList<>();
        inputs.add(matrix1);
        inputs.add(matrix2);

        for (int[][] input : inputs) {
            setZeroes(input);
            System.out.println(Arrays.deepToString(input));
        }
    }

    /**
     * 不使用额外空间，原地修改
     * 关键：使用第 1 行和第 1 列来进行标记
     */
    public static void setZeroes(int[][] matrix) {
        boolean rowFlag = false, colFlag = false;
        int rows = matrix.length, cols = matrix[0].length;

        // 遍历第 1 行，判断是否有 0
        for (int i = 0; i < cols; i++) {
            if (matrix[0][i] == 0) {
                rowFlag = true;
                break;
            }
        }
        // 遍历第 1 列，判断是否有 0
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                colFlag = true;
                break;
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    // 当前行的第一位 置 0
                    matrix[i][0] = 0;
                    // 当前列的第一位 置 0
                    matrix[0][j] = 0;
                }
            }
        }
        // 遍历除第 1 行第 1 列外的其他元素，若元素为 0，则所在列全部置 0
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                // 元素所在行有 0，或者所在列有 0 时，当前元素置 0
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 根据标记，决定第 1 行和第 1 列是否需要全部置 0
        if (rowFlag) {
            // 第 1 行全部置 0
            for (int i = 0; i < cols; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colFlag) {
            // 第 1 列全部置 0
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    public static void setZeroes2(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        // rowFlag[0] = true：第 1 行出现了 0
        boolean[] rowFlag = new boolean[rows];
        // colFlag[3] = true：第 4 列出现了 0
        boolean[] colFlag = new boolean[cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    rowFlag[i] = true;
                    colFlag[j] = true;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (rowFlag[i] || colFlag[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}